public class RBTree {


    static class RBTreeNode{
        public int val ;
       public RBTreeNode left ;
       public RBTreeNode right ;
       public RBTreeNode parent ;
       public COLOR color ;

        public RBTreeNode(int val) {
            this.val = val ;
            // 创建出来的结点默认是红色 ;
            this.color = COLOR.RED;
        }
        // root 结点
        public RBTreeNode root ;

        public boolean insert(int val){
            RBTreeNode node = new RBTreeNode(val);
            if(this.root == null) {
                this.root = node;
                return true;
            }
            RBTreeNode cur = root ;
            RBTreeNode parent = null ;
            while(cur != null){
                parent = cur ;
                if(val > cur.val){
                    cur = cur.right ;
                }else if(val < cur.val){
                    cur = cur.left ;
                }else{
                    return false;   // 重复结点不要
                }
            }
            if(val > parent.val){
                parent.right = node ;
            }else{
                parent.left = node ;
            }
            node.parent = parent;
            cur = node ;
           // 将 node 插入进来后

            // 红黑树 需要调整颜色

             // 当parent为红色, cur为红 需要调整
            while (parent!=null && parent.color==COLOR.RED){
               // parent 是红色, 所以 这个 gp一定不为空
                RBTreeNode grandFather = parent.parent ;

               if(parent == grandFather.left){
                  RBTreeNode uncle = grandFather.right ;
                  if(uncle!=null && uncle.color==COLOR.RED){  // p为gp的左, u存在并且为红色
                      // p , u调整为 黑色
                      parent.color = COLOR.BLACK;
                      uncle.color = COLOR.BLACK;
                      // g 调整为 红色
                      grandFather.color = COLOR.RED;

                      // 向上调整 , 直到 根结点或 parent 不为红
                       cur = grandFather;
                       parent = cur.parent;

                  }else{  // u不存在或为黑色
                      // 情况3, p和cur为红, u不存在或黑 , g 是 黑
                      // 但 cur 是 p 的右 , 左旋, 得到情况 2 ,
                      // 所以要进行情况2的处理前, 先判断是否是情况3
                      if(cur == parent.right){
                          // 左旋
                          rotateLeft(parent);
                          // 将p和cur的引用换回来
                          RBTreeNode tmp = parent ;
                          parent = cur ;
                          cur = tmp;
                      }


                      //情况2 ,p和cur为红 ,  u 不存在或为黑色, g 是黑色
                      // 右旋 g 然后修改 g 和 p 的颜色 ;
                       rotateRight(grandFather);
                       grandFather.color= COLOR.RED;
                       parent.color = COLOR.BLACK;
                  }

               }else{




               }


            }



            return false ;
        }

        // 右旋
        private void rotateRight(RBTreeNode parent) {
            RBTreeNode subL = parent.left ;
            RBTreeNode subLR = subL.right ;
            // parent 变成subL的右子 , subLR 变成parent的左子 ;
            parent.left = subLR ;
            if(subLR != null){
                subLR.parent = parent ;
            }
            if(this.root == parent){
                this.root = subL ;
                this.root.parent = null ;

            }else{
                RBTreeNode pParent = parent.parent ;
                if(parent == pParent.left){
                    subL.parent = pParent ;
                    pParent.left = subL;
                }else{
                    subL.parent = pParent ;
                    pParent.right = subL ;
                }
            }

            parent.parent = subL ;
            subL.right = parent ;

        }
        //左旋
        private void rotateLeft(RBTreeNode parent) {
            RBTreeNode subR = parent.right ;
            RBTreeNode subRL = subR.left ;
            // parent变成 subR的左子 , subRL 变成parent的右子
            parent.right = subRL ;
            if(subRL != null){
                subRL.parent = parent ;
            }
            if(parent == this.root){
                this.root = subR ;
                this.root.parent = null ;
            }else{
                RBTreeNode pParent = parent.parent ;
                if(parent == pParent.left){
                    subR.parent = pParent ;
                    pParent.left = subR;
                }else{
                    subR.parent =  pParent ;
                    pParent.right = subR;
                }
            }

            parent.parent = subR ;
            subR.left = parent ;
        }

    }
}
